package writtenTraining.day37;

import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Scanner;

/**
 * day37:(1)模拟 + 左旋:NC114 旋转字符串
 */


class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * <p>
     * 旋转字符串
     *
     * @param A string字符串
     * @param B string字符串
     * @return bool布尔型
     */
    public boolean solve(String A, String B) {

        // 模拟 + 左旋
        int len1 = A.length(), len2 = B.length();
        // 特殊情况判断
        if (len1 != len2) {
            return false;
        }

        // 进行左旋
        for (int i = 0; i < len1; i++) {
            if (B.equals(spin(A, i))) {
                return true;
            }
        }

        return false;
    }

    private String spin(String s, int index) {
        int len = s.length();

        return s.substring(index + 1, len)
                + s.substring(0, index + 1);

    }
}

/**
 * day37:(2)链表 + 小根堆：NC51 合并k个已排序的链表
 */

class ListNode {
    int val;
    ListNode next = null;

    public ListNode(int val) {
        this.val = val;
    }
}

class Solution1 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param lists ListNode类ArrayList
     * @return ListNode类
     */
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        // 链表 + 小根堆
        ListNode head = new ListNode(-1);
        int sz = lists.size();

        PriorityQueue<ListNode> queue =
                new PriorityQueue<>((a, b) -> a.val - b.val);

        // 加入队列
        for (ListNode node : lists) {
            if (node != null) {
                queue.add(node);
            }
        }

        ListNode ret = head;
        // 开始遍历
        while (!queue.isEmpty()) {
            // 加入
            ListNode node = queue.poll();
            ret.next = node;

            // 调整
            ret = ret.next;
            node = node.next;
            if (node != null) {
                queue.add(node);
            }
        }

        return head.next;
    }
}


/**
 * day37:(3)深度优先遍历 + 记忆化搜索：DP18 滑雪
 */


// 注意类名必须为 Main, 不要有任何 package xxx 信息
 class Main {
    public static int[][] memo = new int[110][110];
    public static int[] dx = {0,0,-1,1};
    public static int[] dy = {-1,1,0,0};
    public static int row = 0,col = 0;
    public static void main(String[] args) {
        // 深度优先遍历 + 记忆化搜索
        Scanner in = new Scanner(System.in);
        row = in.nextInt(); col = in.nextInt();
        int[][] nums = new int[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                nums[i][j] = in.nextInt();
            }
        }

        int ret = -0x3f3f3f3f;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                ret = Math.max(ret,dfs(nums,i,j) + 1);
            }
        }

        // 输出结果
        System.out.println(ret);
    }

    public static int dfs(int[][] nums, int i, int j ) {
        if(memo[i][j] != 0) {
            return memo[i][j];
        }

        int count = 0;
        for(int k = 0; k < 4; k++) {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && x < row
                    && y >= 0 && y < col
                    && nums[x][y] > nums[i][j]) {
                count = Math.max(count,dfs(nums,x,y) + 1);
            }
        }

        memo[i][j] = count;
        return  count;
    }
}





